


# 接雨水



class Solution:

    def trap(self, height):

        # 从左、右分别开始遍历最大值

        n = len(height)
        lefts = [0] * (n + 2)
        rights = [0] * (n + 2)

        for i in range(1, n + 1):
            
            # 从左到右
            lefts[i] = max(lefts[i - 1], height[i - 1])
            # 从右到左
            rights[n - i + 1] = max(rights[n - i + 2], height[n - i])

        ans = 0
        for i in range(n):

            ans += min(lefts[i + 1], rights[i + 1]) - height[i]


        return ans
    

if __name__ == "__main__":

    height = [0,1,0,2,1,0,1,3,2,1,2,1]
    sol = Solution()
    ans = sol.trap(height)
    print(ans)
